﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TheVoiceOfSnake
{
    public class FastFourierTransformer
    {
        private void CalculateValues(ref double[] inReal, ref double[] inImag, FastFourierTransformationType type)
        {
            int i, j, k, n;
            int numBits, blockSize, blockEnd;
            int sampleCount = inReal.Length;
            CorrectInputData(ref sampleCount, ref inReal, ref inImag);

            //int sampleCount = offsetEnd - offset;
            double[] outReal = new double[sampleCount];
            double[] outImag = new double[sampleCount];
            double angle_numerator = 2.0 * Math.PI;
            double tr, ti;

            if (type == FastFourierTransformationType.IFFT)
            {
                angle_numerator = -angle_numerator;
            } 
            numBits = NumberOfBitsNeeded(sampleCount);
            for (i = 0; i < sampleCount; i++)
            {
                j = ReverseBits(i, numBits);
                outReal[j] = inReal[i];
                outImag[j] = (inImag == null) ? 0.0 : inImag[i];
            }
            blockEnd = 1;
            for (blockSize = 2; blockSize <= sampleCount; blockSize <<= 1)
            {
                double delta_angle = angle_numerator / (double)blockSize;
                double sm2 = Math.Sin(-2 * delta_angle);
                double sm1 = Math.Sin(-delta_angle);
                double cm2 = Math.Cos(-2 * delta_angle);
                double cm1 = Math.Cos(-delta_angle);
                double w = 2 * cm1;
                double[] ar = new double[3];
                double[] ai = new double[3];
                for (i = 0; i < sampleCount; i += blockSize)
                {
                    ar[2] = cm2;
                    ar[1] = cm1;
                    ai[2] = sm2;
                    ai[1] = sm1;
                    for (j = i, n = 0; n < blockEnd; j++, n++)
                    {
                        ar[0] = w * ar[1] - ar[2];
                        ar[2] = ar[1];
                        ar[1] = ar[0];
                        ai[0] = w * ai[1] - ai[2];
                        ai[2] = ai[1];
                        ai[1] = ai[0];
                        k = j + blockEnd;
                        tr = ar[0] * outReal[k] - ai[0] * outImag[k];
                        ti = ar[0] * outImag[k] + ai[0] * outReal[k];
                        outReal[k] = outReal[j] - tr;
                        outImag[k] = outImag[j] - ti;
                        outReal[j] += tr;
                        outImag[j] += ti;
                    }
                }
                blockEnd = blockSize;
            }
            if (type == FastFourierTransformationType.IFFT)
            {
                double denom = (double)sampleCount;
                for (i = 0; i < sampleCount; i++)
                {
                    outReal[i] /= denom;
                    outImag[i] /= denom;
                }
            }
            inReal = outReal;
            inImag = outImag;
        }

        private void CorrectInputData(ref int size, ref double[] inReal, ref double[] inImag) 
        {
            int i = 2;
            for (; i < size; i *= 2)
            {
                if (i == size)
                {
                    break;
                }
            }
            size = i;
            if (i != inReal.Length)
            {
                ChangeInputData(size, ref inReal, ref inImag);
            }
        }

        private void ChangeInputData(int size, ref double[] inReal, ref double[] inImag) 
        {
            double[] outReal = new double[size];
            double[] outImag = new double[size];

            if (inImag != null)
            {
                for (int i = 0; i < inImag.Length; i++)
                {
                    outImag[i] = inImag[i];
                }
            }
            else 
            {
                for (int i = 0; i < inReal.Length; i++)
                {
                    outReal[i] = inReal[i];
                }
            }

            inReal = outReal;
            if (inImag != null)
            {
                inImag = outImag;
            }
        }

        public void Transform(List<Frame> frames, FastFourierTransformationType type) 
        { 
            double[] real = new double[frames.First().Size()];
            foreach (var frame in frames) 
            {
                // bez części zespolonej
                double[] imag = null;
                real = frame;
                CalculateValues(ref real, ref imag, type);
                frame.FillComplexValues(real, imag);
                frame.ConvertFromDoubleArray(real);
            }
        }

        private int NumberOfBitsNeeded(int sampleCount)
        {
            int i;
            if (sampleCount < 2)
            {
                return 0;
            }
            for (i = 0; ; i++)
            {
                if ((sampleCount & (1 << i)) > 0) return i;
            }
        }

        private int ReverseBits(int index, int numBits)
        {
            int i, rev;
            for (i = rev = 0; i < numBits; i++)
            {
                rev = (rev << 1) | (index & 1);
                index >>= 1;
            }
            return rev;
        }
    }
}
